A transaction is assumed to be a sequence of one or more computer operations, also herein termed computer steps, performed by a computing system, which change a state of the system. Methods for processing transactions, and in particular for recovering “gracefully” from a failure in such processing, are very well known in the art. Transaction Processing: Concepts and Techniques, by Gray and Reuter, published by Morgan Kaufmann Publishers, San Mateo Calif. (1993), describes transactions and their processing in detail, and sections 1.2 and chapter 10, respectively entitled “What Is a Transaction Processing System,” and “Transaction Manager Concepts,” are incorporated herein by reference.
As stated in the above-referenced section 1.2, a transaction has the properties of Atomicity, Consistency, Isolation, and Durability (ACID). The properties are described in section 1.2, and may be summarized as follows:
AtomicityEither all operations happen or nonehappen.ConsistencyThe transaction must result in acorrect transformation of the state.The transaction must be a “correctprogram.”IsolationEven though transactions executeconcurrently, it appears to eachtransaction, T, that others executedeither before T or after T.DurabilityOnce a transaction completessuccessfully (commits), its changes tothe state survive failures.
A transaction manager, which may comprise one or more sub-managers, depending on the computing system in which the transaction is being executed, monitors the progress of the transaction. By monitoring the transaction, the manager ensures that the ACID properties are complied with and also enables the possibility of a graceful recovery if a failure occurs during the transaction process. To perform the required monitoring, transaction managers known in the art save information concerning the computing system at various points of the transaction, such as at the beginning of the transaction, and at save points during the transaction. The save points are typically specified by a transaction protocol under which the transaction is processed.
The size of the information saved varies according to the protocol, and in protocols known in the art the size is of the order of the total size of variables involved in the transaction, or of the number of computer operations of the transaction. Chapter 10 of Transaction Processing: Concepts and Techniques describes a “DO-UNDO-REDO” protocol, in which information termed a transaction log is stored during the transaction process (the “DO” phase). The transaction manager can UNDO the transaction—typically necessary if it is determined that one of the ACID properties has not been complied with—by undoing each of the logged individual actions in a reverse order from the most recently logged action. The transaction manager can REDO the transaction—typically to recover from a system failure—by redoing logged actions in a forward direction.
Computer operations and processes may be classified as idempotent or non-idempotent. An operation is idempotent if performing the operation more than one time gives the same result as performing the operation once; conversely, an operation is non-idempotent if repeating the operation gives a different result. Thus, the operation “set my account to be $1,000 in credit” is idempotent, whereas the operation “add $1,000 to my account” is not. A process is idempotent if it comprises only idempotent operations.
In chapter 10, Gray and Reuter discuss formulating transactions with idempotence in mind, describing, for example, a method of transaction logging termed value logging. Value logging records both old values and new values of object states, so that each operation using the log is idempotent, and operating either an UNDO or a REDO process using the log renders both processes idempotent.